#pragma once

#include <string.h>
#include <memory>

// Custom allocator, stops us from dynamically allocating memory which is bad for time-travel.
// While vector has a resize() function, the others don't,
// and we need the memory to be allocated during the init of the container.
// This will might have a performance hit over the regular std::allocator.
// Optimizations are welcome.
// -- Warepire


// Use for array-based containers, like Vector
template <class T, size_t szSlots = 0>
class StaticAllocator
{
protected:
	size_t szSlotsAllocated;
	size_t szSlotsInUse;
	size_t szSlotSize;
	T* array;

public:
	typedef T			value_type;
	typedef value_type*		pointer;
	typedef const value_type*	const_pointer;
	typedef value_type&		reference;
	typedef const value_type&	const_reference;
	typedef std::size_t		size_type;
	typedef std::ptrdiff_t		difference_type;

	StaticAllocator()
	{
		if(szSlots > 0) array = new T(szSlots);
		szSlotsAllocated = szSlots;
		szSlotsInUse = 0;
		szSlotSize = sizeof(T);
	}

	~StaticAllocator()
	{
		if(szSlotsAllocated > 0) delete [] array;
	}

	pointer address(reference x) const
	{
		return &x;
	}
	const_pointer address(const_reference x) const
	{
		return &x;
	}

	virtual pointer allocate (size_type n, allocator<void>::const_pointer hint = 0)
	{
		if((szSlotsInUse + n) < szSlotsAllocated)
		{
			pointer rv = array[szSlotsInUse];
			szSlotsInUse += n;
			return rv;
		}
		throw std::bad_alloc();
	}

	virtual void deallocate (pointer p, size_type n)
	{
		if((szSlotsInuse - n) < 0) szSlotsInUse = 0;
		else szSlotsInUse -= n;
	}
	
	size_type max_size() const throw()
	{
		return szSlotsAllocated;
	}

	void construct (pointer p, const_reference val)
	{
		p = value_type(val); // Can memcpy be used instead? (memcpy(p, val, szSlotSize);)
	}

	void destroy (pointer p)
	{
		p->~value_type();
	}
};

// Use for binary tree based containers like Map and Set.
template <class T, size_t szSlots = 0>
class StaticTreeAllocator : public StaticAllocator<T, szSlots>
{
private:
	char* arrAllocated;

public:

	StaticTreeAllocator()
	{
		StaticAllocator(); // Absolutely make sure this is called first!
		if(szSlotsAllocated > 0) arrAllocated = new char[szSlotsAllocated];
		memset(arrAllocated, 0x00, szSlotsAllocated); // Mark them all as unallocated.
	}
	
	~StaticTreeAllocator() // During the destruction the order is not important.
	{
		if(szSlotsAllocated > 0) delete [] arrAllocated;
	}

	pointer allocate (size_type n, allocator<void>::const_pointer hint = 0)
	{
		if((n == 1) && ((szSlotsInUse + n) < szSlotsAllocated))
		{
			szSlotsInUse += n;
		}
		else throw std::bad_alloc();

		size_t slot = 0;
		while(arrAllocated[slot] == 0x01 && slot < szSlotsAllocated) slot++;
		
		arrAllocated[slot] = 0x01;
		return &(array[slot]);
		
	}

	virtual void deallocate (pointer p, size_type n)
	{
		StaticAllocator::deallocate(p, n);

		size_t pos = p - array;
		arrAllocated[pos] = 0x00;
	}
};